{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Jumps to Reach the Last Index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumJumps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #达到末尾下标所需的最大跳跃次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、由 <code>n</code> 个整数组成的数组 <code>nums</code> 和一个整数 <code>target</code> 。</p>\n",
    "\n",
    "<p>你的初始位置在下标 <code>0</code> 。在一步操作中，你可以从下标 <code>i</code> 跳跃到任意满足下述条件的下标 <code>j</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt; n</code></li>\n",
    "\t<li><code>-target &lt;= nums[j] - nums[i] &lt;= target</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>返回到达下标 <code>n - 1</code> 处所需的 <strong>最大跳跃次数</strong> 。</p>\n",
    "\n",
    "<p>如果无法到达下标 <code>n - 1</code> ，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,3,6,4,1,2], target = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：\n",
    "- 从下标 0 跳跃到下标 1 。 \n",
    "- 从下标 1 跳跃到下标 3 。 \n",
    "- 从下标 3 跳跃到下标 5 。 \n",
    "可以证明，从 0 到 n - 1 的所有方案中，不存在比 3 步更长的跳跃序列。因此，答案是 3 。 </pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,3,6,4,1,2], target = 3\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>要想以最大跳跃次数从下标 0 到下标 n - 1 ，可以按下述跳跃序列执行操作：\n",
    "- 从下标 0 跳跃到下标 1 。 \n",
    "- 从下标 1 跳跃到下标 2 。 \n",
    "- 从下标 2 跳跃到下标 3 。 \n",
    "- 从下标 3 跳跃到下标 4 。 \n",
    "- 从下标 4 跳跃到下标 5 。 \n",
    "可以证明，从 0 到 n - 1 的所有方案中，不存在比 5 步更长的跳跃序列。因此，答案是 5 。 </pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,3,6,4,1,2], target = 0\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>可以证明不存在从 0 到 n - 1 的跳跃序列。因此，答案是 -1 。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length == n &lt;= 1000</code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= nums[i]&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>0 &lt;= target &lt;= 2 * 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-jumps-to-reach-the-last-index](https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-jumps-to-reach-the-last-index](https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,6,4,1,2]\\n2', '[1,3,6,4,1,2]\\n3', '[1,3,6,4,1,2]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        # 1, 100, -100, -100, -100, target = 100\n",
    "        # if greedy, then 1 -> 100 -> nowhere, so greedy doesn't work\n",
    "        dp = [-1] * len(nums)\n",
    "        dp[0] = 0\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            maxjumps = -1\n",
    "            for j in range(i):\n",
    "                if abs(nums[j] - nums[i]) <= target and dp[j] != -1:\n",
    "                    maxjumps = max(maxjumps, dp[j] + 1)\n",
    "            dp[i] = maxjumps\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [float('-inf')] * n\n",
    "        dp[0] = 0\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "\n",
    "        \n",
    "        if dp[-1] == float('-inf'):\n",
    "            return -1\n",
    "        else:\n",
    "            return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1] * n\n",
    "        dp[0] = 0\n",
    "        for j in range(1, n):\n",
    "            for i in range(0, j):\n",
    "                if dp[i] == -1: continue\n",
    "                tmp = nums[j] - nums[i]\n",
    "                tmp = tmp if tmp > 0 else -tmp\n",
    "                if tmp <= target:\n",
    "                    if dp[j] == -1: dp[j] = dp[i] + 1\n",
    "                    else: dp[j] = dp[j] if dp[j] > dp[i] + 1 else dp[i] + 1\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target and f[j]:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "        return f[-1] -1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * n\n",
    "        f[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "        return -1 if f[-1] < 0 else f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            a = -1\n",
    "            for j in range(i):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(nums[i] - nums[j]) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        time=[0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if (i==0 and abs(nums[j]-nums[i]) <=target) or (time[i]!=0 and abs(nums[j]-nums[i]) <=target):\n",
    "                    time[j]=max(time[i]+1,time[j])\n",
    "           \n",
    "        return time[-1] if time[-1] else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        \"\"\"\n",
    "        思考:\n",
    "        dp[i]: 从0跳到i所需的最大跳跃次数\n",
    "        对于i, 只有符合abs(nums[i]-nums[j])<=target条件的点j才能跳到i,\n",
    "        所以如果存在几个这样的点j1,j2,j3...那么找到最大的dp[j], dp[i] = max dp[j] + 1\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        dp = [-1] * n\n",
    "        dp[0] = 0\n",
    "        for end in range(1, n):\n",
    "            steps = -1\n",
    "            for start in range(end-1, -1, -1):\n",
    "                if dp[start] != -1 and abs(nums[end]-nums[start]) <= target:\n",
    "                    steps = max(steps, dp[start]+1)\n",
    "            dp[end] = steps\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            a = -1\n",
    "            for j in range(i):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(nums[i] - nums[j]) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums, k):\n",
    "        # Write Code Here \n",
    "        # 动态规划\n",
    "        # 最长的步数\n",
    "        \n",
    "        n = len(nums)\n",
    "        # dp 用于存储从0到i的最大步数\n",
    "        dp = [-1] * n\n",
    "        dp[0] = 0\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            # 遍历返回0 ， i - 1，找到满足条件的j，使得dp[j]最大\n",
    "            for j in range(i):\n",
    "                # 如果abs(nums[i]-nums[j])<=k,则可以从j跳到i\n",
    "                if abs(nums[i]-nums[j])<=k and dp[j] != -1:\n",
    "                    # 更新i，选择最大的\n",
    "                    dp[i] = max(dp[i], dp[j]+1)\n",
    "        \n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "    l = len(nums)\n",
    "    dp = [-1] * l\n",
    "    dp[0] = 0\n",
    "    for i in range(1, l):\n",
    "      vi = nums[i]\n",
    "      for j in range(i - 1, -1, -1):\n",
    "        vj = nums[j]\n",
    "        if dp[j] != -1 and abs(vi - vj) <= target:\n",
    "          dp[i] = max(dp[i], dp[j] + 1)\n",
    "    # print(f\"dp {dp}\")\n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            a = -1\n",
    "            for j in range(i):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(nums[i] - nums[j]) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [float('-inf')]*len(nums)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            # print(dp)\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if -target <= nums[j] - nums[i] <= target:\n",
    "                    dp[j] = max(dp[j], dp[i]+1)\n",
    "\n",
    "        # print(dp)\n",
    "        return dp[-1] if dp[-1] != float('-inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            a = -1\n",
    "            for j, n2 in enumerate(nums[:i]):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(n - n2) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] + [-1] * (n - 1)\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target and dp[j] != -1:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dist = [-1]*n\n",
    "        dist[0] = 0\n",
    "        # dist[i] 从0到i的最大长度\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i]-nums[j]) <= target:\n",
    "                        dist[i] = max(dist[i],dist[j]+1)\n",
    "                if dist[i] == 0:\n",
    "                    dist[i] = -1\n",
    "        return dist[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [-1] * len(nums)\n",
    "        dp[0] = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    if dp[i] == -1:\n",
    "                        continue\n",
    "                    dp[j] = max(dp[j], dp[i] + 1)\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        arr = [0] * n\n",
    "        arr[0] = 1\n",
    "        for i in range(1,n):\n",
    "            for j in range (0,i):\n",
    "                if arr[j]>0 and abs(nums[j]-nums[i])<=target:\n",
    "                    arr[i] = max(arr[i],arr[j]+1)\n",
    "        return arr[-1]-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1] * n\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if dp[j] != -1 and abs(nums[i] - nums[j]) <= target:\n",
    "                    # print(i, j)\n",
    "                    # print(\"y\", abs(nums[i] - nums[j]), target)\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        # print(dp)\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n \n",
    "        for i in range(n-2, -1, -1):\n",
    "            tmp = -1\n",
    "            for j in range(i+1, n):\n",
    "                if abs(nums[j] - nums[i]) <= target:\n",
    "                    tmp = max(tmp, dp[j])\n",
    "            if tmp >= 0:\n",
    "                dp[i] = tmp + 1\n",
    "            else:\n",
    "                dp[i] = -1\n",
    "        return dp[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "    l = len(nums)\n",
    "    dp = [-1] * l\n",
    "    dp[0] = 0\n",
    "    for i in range(1, l):\n",
    "      vi = nums[i]\n",
    "      for j in range(i - 1, -1, -1):\n",
    "        vj = nums[j]\n",
    "        if dp[j] != -1 and abs(vi - vj) <= target:\n",
    "          dp[i] = max(dp[i], dp[j] + 1)\n",
    "    # print(f\"dp {dp}\")\n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-1] * n\n",
    "        f[0] = 0\n",
    "        for i in range(n):\n",
    "            if f[i] == -1:\n",
    "                continue\n",
    "            for j in range(i + 1, n):\n",
    "                if -target <= nums[j] - nums[i] <= target:\n",
    "                    f[j] = max(f[j], f[i] + 1)\n",
    "        return f[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-inf]*n\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i]-nums[j])<=target:\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\n",
    "        return dp[-1] if dp[-1]>0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        f=[-inf]*n\n",
    "        f[0]=0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i]-nums[j])<=target:\n",
    "                    f[i]=max(f[i],f[j]+1)\n",
    "        return -1 if f[-1]<0 else f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1]*n\n",
    "        dp[0] = 0\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if dp[j]!=-1 and abs(nums[i]-nums[j])<=target:\n",
    "                    dp[i] = max(dp[i],dp[j]+1)\n",
    "        print(dp)\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        self.glob_result=[]\n",
    "        self.glob_jump_count=[-1 for i in range(len(nums))]\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            cur_jumps=[]\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if j==len(nums)-1:\n",
    "                    if nums[j]-nums[i]<=target and nums[j]-nums[i]>=-target:\n",
    "                        cur_jumps.append(1)\n",
    "                else:\n",
    "                    if self.glob_jump_count[j]!=-1:\n",
    "                        if nums[j] - nums[i] <= target and nums[j] - nums[i] >= -target:\n",
    "                            cur_jumps.append(self.glob_jump_count[j]+1)\n",
    "\n",
    "            if cur_jumps:\n",
    "                self.glob_jump_count[i]=max(cur_jumps)\n",
    "        return self.glob_jump_count[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0 for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if i!=n-1 and dp[i]==0:\n",
    "                continue\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if -target<=nums[j]-nums[i]<=target:\n",
    "                    dp[j]=max(dp[j],dp[i]+1)\n",
    "        if dp[0]==0:\n",
    "            return -1\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        # 记录头到相应点最大跳跃次数\n",
    "        dp = [-1]*len(nums)\n",
    "        dp[0] = 0\n",
    "        # 外层循环，对应相应点\n",
    "        for r in range(1, len(nums)):\n",
    "            for l in range(r):\n",
    "                if dp[l] != -1 and abs(nums[r] - nums[l]) <= target:\n",
    "                    dp[r] = max(dp[r], dp[l]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * n\n",
    "        f[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "        return -1 if f[-1] < 0 else f[-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [-1] * len(nums)\n",
    "        dp[0] = 0\n",
    "        if abs(nums[1] - nums[0]) <= target:\n",
    "            dp[1] = 1\n",
    "        for i in range(2, len(nums)):\n",
    "            for j in range(i):\n",
    "                if dp[j] == -1:\n",
    "                    continue\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "    l = len(nums)\n",
    "    dp = [-1] * l\n",
    "    dp[0] = 0\n",
    "    for i in range(1, l):\n",
    "      vi = nums[i]\n",
    "      for j in range(i - 1, -1, -1):\n",
    "        vj = nums[j]\n",
    "        if dp[j] != -1 and abs(vi - vj) <= target:\n",
    "          dp[i] = max(dp[i], dp[j] + 1)\n",
    "    # print(f\"dp {dp}\")\n",
    "    return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * n\n",
    "        f[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "        return -1 if f[-1] < 0 else f[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * n\n",
    "        f[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target and f[j] + 1 > f[i]:\n",
    "                    f[i] = f[j] + 1\n",
    "        return -1 if f[-1] < 0 else f[-1]\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, a: List[int], x: int) -> int:\n",
    "        n=len(a)\n",
    "        ans=[-1]*n\n",
    "        ans[0]=0\n",
    "        for i in range(n):\n",
    "            if ans[i]>=0:\n",
    "                for j in range(i+1,n):\n",
    "                    if abs(a[i]-a[j])<=x:\n",
    "                        ans[j]=max(ans[j],ans[i]+1)\n",
    "        return ans[-1]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        size = len(nums)\n",
    "        # print(nums)\n",
    "        cnt = [0] * size\n",
    "        cnt[0] = 1\n",
    "        for i in range(size):\n",
    "            if not cnt[i]:\n",
    "                continue\n",
    "            n = []\n",
    "            for j in range(i + 1, size):\n",
    "                if -target <= nums[j] - nums[i] <= target:\n",
    "                    n.append(j)\n",
    "            # print(cnt[i], i, n)\n",
    "            for j in n:\n",
    "                cnt[j] = max(cnt[i] + 1, cnt[j])\n",
    "            # print(cnt)\n",
    "        if cnt[-1] == 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return cnt[-1] - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            a = -2\n",
    "            for j, n2 in enumerate(nums[:i]):\n",
    "                if dp[j] != -1 and abs(n - n2) <= target and dp[j] > a:  # 寻找可以到达该位置的跳跃数最大的值\n",
    "                    a = dp[j]\n",
    "            dp[i] = a + 1\n",
    "        return dp[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1] * n\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if (abs(nums[j] - nums[i]) <= target and dp[j] >= 0):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        f=[0]*n;f[0]=1\n",
    "        for i in range(1,n):\n",
    "            for j in range(i):\n",
    "                if(f[j] and -target<=nums[i]-nums[j]<=target):f[i]=max(f[i],f[j]+1)\n",
    "        return (f[n-1]-1) if f[n-1] else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * n\n",
    "        f[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    f[i] = max(f[i], f[j] + 1)\n",
    "        return -1 if f[-1] < 0 else f[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [-inf] * n\n",
    "        f[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    f[i] = max(f[i], f[j]+1)\n",
    "        return -1 if f[-1] < 0 else f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        for i in range(1, n):\n",
    "            a = -1\n",
    "            for j in range(i):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(nums[i] - nums[j]) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        for i in range(1,n):\n",
    "            dp[i]=-1\n",
    "            for j in range(i):\n",
    "                if -target<=nums[i]-nums[j]<=target and dp[j]>=0:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-inf] * n \n",
    "        dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[-1] if dp[-1] != -inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[-1]*n\n",
    "        dp[0]=0\n",
    "        last=nums[0]\n",
    "        for i in range(1,n):\n",
    "            max_val=-1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if abs(nums[i]-nums[j])<=target and dp[j]>max_val:\n",
    "                    dp[i]=dp[j]+1\n",
    "                    max_val=dp[j]\n",
    "                \n",
    "        return dp[-1]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            a = -1\n",
    "            for j, n2 in enumerate(nums[:i]):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(n - n2) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            a = -1\n",
    "            for j, n2 in enumerate(nums[:i]):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(n - n2) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     if i == len(nums) - 1:\n",
    "        #         return 0\n",
    "        #     res = -inf\n",
    "        #     for j in range(i+1,len(nums)):\n",
    "        #         if abs(nums[j]-nums[i]) <= target:\n",
    "        #             res = max(res,dfs(j) + 1)\n",
    "        #     return res\n",
    "        # ans = dfs(0)\n",
    "        # return -1 if ans < 0 else ans\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [-inf]*n\n",
    "        dp[0] = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if abs(nums[j]-nums[i]) <= target:\n",
    "                    dp[i] = max(dp[i],dp[j] + 1)\n",
    "        \n",
    "        return -1 if dp[-1] < 0 else dp[-1]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [-inf] * len(nums)\n",
    "        dp[0] = 0\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            for j, n2 in enumerate(nums[:i]):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(n - n2) <= target and dp[j] + 1 > dp[i]: \n",
    "                    dp[i] = dp[j] + 1\n",
    "        return -1 if dp[-1] < 0 else dp[-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1] * n \n",
    "        dp[-1] = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            tmp = -1\n",
    "            for j in range(i+1, n):\n",
    "                if abs(nums[j] - nums[i]) <= target:\n",
    "                    tmp = max(tmp, dp[j])\n",
    "            dp[i] = tmp + 1 if tmp >= 0 else -1 \n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1] * n\n",
    "        dp[0] = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if dp[j] >= 0:\n",
    "                    if abs(nums[j] - nums[i]) <= target:\n",
    "                        if dp[i] == -1:\n",
    "                            dp[i] = dp[j] + 1\n",
    "                        else:\n",
    "                            dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[-1]\n",
    "                     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [-1 for i in range(len(nums))]\n",
    "        dp[0] = 0\n",
    "        for i in range(len(nums)):\n",
    "            if dp[i] != -1:\n",
    "                for j in range(i+1, len(nums)):\n",
    "                    if -target <= nums[j] - nums[i] <= target:\n",
    "                        dp[j] = max(dp[j], dp[i]+1)\n",
    "        \n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        for i, n in enumerate(nums[1:], 1):\n",
    "            a = -1\n",
    "            for j, n2 in enumerate(nums[:i]):\n",
    "                 # 寻找可以到达该位置的跳跃数最大的值\n",
    "                if abs(n - n2) <= target and dp[j] > a: \n",
    "                    a = dp[j]\n",
    "            dp[i] = a + (a > -1)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            for j in range(i):\n",
    "                if abs(nums[j] - nums[i]) <= target and (dp[j] != 0 or j==0):\n",
    "                    dp[i] = max(dp[i], dp[j] + 1)\n",
    "        return dp[len(nums) - 1] if dp[len(nums) - 1] != 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(idx):\n",
    "            if idx == n - 1:\n",
    "                return 0\n",
    "            ret = -1\n",
    "            for i in range(idx + 1, n):\n",
    "                if abs(nums[idx] - nums[i]) <= target:\n",
    "                    k = dfs(i)\n",
    "                    if k != -1:\n",
    "                        ret = max(k + 1, ret)\n",
    "            return ret\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i==0:return 0\n",
    "            \n",
    "            res=-inf;\n",
    "            for j in range(i): \n",
    "                if -target<=nums[j]-nums[i]<=target:\n",
    "                    res=max(res,dfs(j)+1)\n",
    "            return res\n",
    "        ans=dfs(n-1)\n",
    "        return ans if ans>0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            res=-inf\n",
    "            for j in range(i):\n",
    "                if abs(nums[i]-nums[j]) <= target:\n",
    "                    res=max(res,dfs(j)+1)\n",
    "            return res\n",
    "        ans=dfs(n-1)\n",
    "        return -1 if ans == -inf else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0: return 0\n",
    "            ans = -inf\n",
    "            for j in range(i):\n",
    "                if abs(nums[j] - nums[i]) <= target:\n",
    "                    ans = max(ans, dfs(j) + 1)\n",
    "            return ans\n",
    "        ans = dfs(n - 1)\n",
    "        return ans if ans != -inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        # ans = [0] * n\n",
    "        #\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ans = -inf\n",
    "            for j in range(i):\n",
    "                if -target <= nums[j] - nums[i] <= target:\n",
    "                    ans = max(ans, dfs(j) + 1)\n",
    "            return ans\n",
    "        return dfs(n-1) if dfs(n-1) >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(n):\n",
    "            if n == len(nums)-1:\n",
    "                return 0\n",
    "            else:\n",
    "                res_num = -1\n",
    "                for i in range(n+1,len(nums)):\n",
    "                    if  nums[n]-target <= nums[i] <= nums[n] + target:\n",
    "                        res_num = max(res_num,dfs(i))\n",
    "                if res_num == -1:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return res_num + 1  \n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(j):\n",
    "            if j == 0:\n",
    "                return 0\n",
    "            res = -math.inf\n",
    "            for i in range(j):\n",
    "                if abs(nums[j] - nums[i]) <= target:\n",
    "                    res = max(res, dfs(i) + 1)\n",
    "            return res\n",
    "\n",
    "        ans = dfs(len(nums) - 1)\n",
    "        return ans if ans > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    res = max(res, dfs(j) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(nums)-1)\n",
    "        return -1 if ans < 0 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==0:\n",
    "                return 0\n",
    "            res=-inf\n",
    "            for j in range(i):\n",
    "                if abs(nums[i]-nums[j])<=target:\n",
    "                    res=max(res,dfs(j)+1)\n",
    "            return res\n",
    "        ans=dfs(len(nums)-1)\n",
    "        return -1 if ans<0 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 怎么判断跳不到\n",
    "        #跳到第 i 个位置的最大跳跃次数\n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            # 边界条件\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            #返回值\n",
    "            res = -inf\n",
    "            #递归到哪里\n",
    "            for j in range(i):\n",
    "                if -target <= nums[j] - nums[i] <= target:\n",
    "                    res = max(res, dfs(j) + 1)\n",
    "            return res\n",
    "        #递归入口\n",
    "        ans = dfs(n - 1)\n",
    "        return ans if ans != -inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==n-1:\n",
    "                return 0\n",
    "            ans=0\n",
    "            for j in range(i+1,n):\n",
    "                if abs(nums[j]-nums[i])<=target:\n",
    "                    if dfs(j)!=inf:\n",
    "                        ans=max(ans,1+dfs(j))\n",
    "            if ans==0:\n",
    "                return inf\n",
    "            return ans\n",
    "        return dfs(0) if dfs(0)!=inf else -1\n",
    "            \n",
    "            \n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "       n=len(nums)\n",
    "       @cache \n",
    "       def g(i):\n",
    "           if i==n-1:\n",
    "               return 0\n",
    "           res=-inf\n",
    "           for j in range(i+1,n):\n",
    "              if abs(nums[j]-nums[i])<=target:\n",
    "                 res=max(g(j)+1,res)\n",
    "           return res\n",
    "       return g(0) if g(0)!=-inf else -1 \n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n - 1: return 0\n",
    "            ans = -inf\n",
    "            for j in range(i + 1, n):\n",
    "                if abs(nums[j] - nums[i]) <= target:\n",
    "                    ans = max(ans, dfs(j) + 1)\n",
    "            return ans\n",
    "        ans = dfs(0)\n",
    "        return ans if ans != -inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==n-1:\n",
    "                return 0\n",
    "            ans=0\n",
    "            flag=0\n",
    "            for j in range(i+1,n):\n",
    "                if abs(nums[j]-nums[i])<=target:\n",
    "                    if dfs(j)!=inf:\n",
    "                        flag+=1\n",
    "                        ans=max(ans,1+dfs(j))\n",
    "            if flag==0:\n",
    "                return inf\n",
    "            if flag>0:\n",
    "                return ans\n",
    "        return dfs(0) if dfs(0)!=inf else -1\n",
    "            \n",
    "            \n",
    "                \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i >= n - 1: return 0\n",
    "            ans = -inf\n",
    "            for j in range(i + 1, n):\n",
    "                if abs(nums[j] - nums[i]) <= target:\n",
    "                    ans = max(ans, dfs(j) + 1)\n",
    "            return ans\n",
    "        ans = dfs(0)\n",
    "        return ans if ans != -inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        # ans = [0] * n\n",
    "        #\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ans = -inf\n",
    "            for j in range(i):\n",
    "                if -target <= nums[j] - nums[i] <= target:\n",
    "                    t = dfs(j)\n",
    "                    if t >= 0:\n",
    "                        ans = max(ans, t)\n",
    "            return ans + 1 if ans >= 0 else -inf\n",
    "        return dfs(n-1) if dfs(n-1) >= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        @cache #用于记忆化\n",
    "        def dfs(i): #dfs函数用于遍历灭一个节点\n",
    "            if i == 0: #跳到了开头\n",
    "                return 0\n",
    "            res = -inf #代表初始值为负数 \n",
    "            for j in range(i):\n",
    "                if(abs(nums[j] - nums[i]) <= target):\n",
    "                    res = max(res,dfs(j) + 1) #结果为res与往前跳一位的最大值\n",
    "            return res\n",
    "        ans = dfs(n-1) #返回结果\n",
    "        #如果ans是负数就返回-1，否则返回res\n",
    "        return -1 if ans<0 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "\n",
    "        n=len(nums)\n",
    "\n",
    "        @cache\n",
    "        def zz(i,j):\n",
    "            if i==n-1:\n",
    "                return 0\n",
    "\n",
    "            res = -inf\n",
    "            for p in range(i+1,n):\n",
    "                if abs(nums[p]-j) <= target:\n",
    "                    res= max(res,zz(p,nums[p]) + 1 )\n",
    "            return res\n",
    "        \n",
    "        res= -inf\n",
    "        for p in range(1,n):\n",
    "            if abs(nums[p]-nums[0]) <= target:\n",
    "                res=max(res, zz(p, nums[p])+1)\n",
    "        \n",
    "        return res if res>=0 else -1\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        # 动态规划 -> 记忆化搜索\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            count = -inf\n",
    "            for j in range(i):\n",
    "                if abs(nums[i] - nums[j]) <= target:\n",
    "                    count = max(count, dfs(j) + 1)\n",
    "            return count\n",
    "        \n",
    "        res = dfs(len(nums) - 1)\n",
    "\n",
    "        return res if res != -inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        #枚举\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i==0:\n",
    "                return 0\n",
    "            res=-inf\n",
    "            for j in range(i):\n",
    "                if abs(nums[j]-nums[i])<=target:\n",
    "                    res=max(res,dfs(j)+1)\n",
    "            return res\n",
    "        ans =dfs(len(nums)-1)\n",
    "        return ans if ans>0 else -1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from typing import List\n",
    "from math import inf\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for j in range(i):\n",
    "                if -target <= nums[i] - nums[j] <= target:\n",
    "                    res = max(res, dfs(j) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(nums) - 1)\n",
    "        return -1 if ans < 0 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for j in range(i):\n",
    "                if -target <= nums[i] - nums[j] <= target:\n",
    "                    res = max(res, dfs(j) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(nums) - 1)\n",
    "        return -1 if ans < 0 else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumJumps(self, nums: List[int], target: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            res = -inf\n",
    "            for j in range(i):\n",
    "                if -target <= nums[i] - nums[j] <= target:\n",
    "                    res = max(res, dfs(j) + 1)\n",
    "            return res\n",
    "        ans = dfs(len(nums) - 1)\n",
    "        return -1 if ans < 0 else ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
